การแปลงจากโพสต์ฟิกซ์เป็นพรีฟิกซ์

วัตถุประสงค์

เป้าหมายของคุณคือการแปลง นิพจน์แบบโพสต์ฟิกซ์ (โนเตชันรีเวิร์สโปลิช) ให้กลายเป็น นิพจน์แบบพรีฟิกซ์ (โนเตชันโปลิช) โดยการสร้างและเดินผ่านต้นไม้แสดงนิพจน์

อัลกอริธึม

1. สร้างต้นไม้แสดงนิพจน์: ประมวลผลนิพจน์โพสต์ฟิกซ์จากซ้ายไปขวา โดยใช้สแต็ค
   • เมื่อพบ ตัวดำเนินการ (ตัวแปร) (เช่น A, B) ให้สร้างต้นไม้ที่มีโหนดเดียวสำหรับมัน และใส่ลงในสแต็ค
   • เมื่อพบ ตัวดำเนินการ (เช่น +, *) ให้ดึงต้นไม้สองต้นออกจากสแต็ค ต้นแรกที่ดึงออกจะเป็นลูกขวามือ (T₂) และต้นที่สองคือลูกซ้ายมือ (T₁) สร้างต้นไม้ใหม่โดยใช้ตัวดำเนินการเป็นราก และใส่กลับเข้าสู่สแต็ค
2. สร้างสตริงพรีฟิกซ์: หลังจากประมวลผลทุกโทเค็นแล้ว สแต็คจะเก็บต้นไม้แสดงนิพจน์ครบถ้วน ให้ดำเนินการ การเดินผ่านแบบพรีออร์เดอร์ (ราก → ซ้าย → ขวา) บนต้นไม้นี้ เพื่อสร้างนิพจน์พรีฟิกซ์สุดท้าย

ตัวอย่าง

สำหรับนิพจน์โพสต์ฟิกซ์ A B + C * อัลกอริธึมจะสร้างต้นไม้ดังนี้:

  *
   / \
  +   C
 / \
A   B

การเดินผ่านแบบพรีออร์เดอร์จะได้ผลลัพธ์เป็นนิพจน์พรีฟิกซ์: * + A B C.

รูปแบบการรับ-ส่งข้อมูล (I/O)

ข้อมูลนำเข้า

• บรรทัดที่ 1:จำนวนเต็ม N (1 ≤ N ≤ 1000), จำนวนโทเค็น
• บรรทัดที่ 2:นิพจน์โพสต์ฟิกซ์ ซึ่งมี N โทเค็น แยกด้วยช่องว่าง

กฎของโทเค็น

• ตัวแปร (ตัวดำเนินการ): ตัวอักษรใหญ่เพียงตัวเดียว (A-Z)
• ตัวดำเนินการ: ตัวดำเนินการไบนารีสี่ตัว: +, -, *, /.

ข้อมูลส่งออก

• บรรทัดเดียวที่มีนิพจน์พรีฟิกซ์ที่สอดคล้องกัน โดยโทเค็นแต่ละตัวคั่นด้วยช่องว่าง

ตัวอย่าง

ตัวอย่างที่ 1:

5

A B + C *

* + A B C

ตัวอย่างที่ 2:

7

A B C * + D /

/ + A * B C D

ตัวอย่างที่ 3:

7

A B + C D - *

* + A B - C D

ข้อจำกัด